{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "8641c8d6-19c9-4aeb-a99d-25306a641f3d",
   "metadata": {},
   "source": [
    "# 插入排序"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99a606af-263a-4cd3-98a4-76b862422380",
   "metadata": {},
   "source": [
    "插入排序的时间复杂度也是 $O(n^2)$，但原理稍有不同。它在列表较低的一端维护一个有序的子列表，并逐个将每个新元素“插入”这个子列表。下图展示了插入排序的过程。深色元素代表有序子列表中的元素。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9f05d63d-cf85-49fc-ba0f-03129b448d77",
   "metadata": {},
   "source": [
    "![插入排序](insertion_sort.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "499cf712-94c0-44c8-9cb0-72592cf2af41",
   "metadata": {},
   "source": [
    "首先假设位置 0 处的元素是只含单个元素的有序子列表。从元素 1 到元素 n–1，每一轮都将当前元素与有序子列表中的元素进行比较。在有序子列表中，将比它大的元素右移；当遇到一个比它小的元素或抵达子列表终点时，就可以插入当前元素。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "00650ddd-44ec-4c0a-a649-b8bedc2d6baf",
   "metadata": {},
   "source": [
    "下图详细展示了第 5 轮遍历的情况。此刻，有序子列表包含 5 个元素：17、26、54、77 和 93。现在想插入 31。第一次与 93 比较，结果是将 93 向右移；同理，77 和 54 也向右移。遇到 26 时，就不移了，并且 31 找到了正确位置。现在，有序子列表有 6 个元素。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cf37207a-9ffb-4b8e-9025-fc44b251f2e8",
   "metadata": {},
   "source": [
    "![插入排序第5轮](insertion_sort2.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c4cb3a38-0131-49cf-9c48-19fb13919863",
   "metadata": {},
   "source": [
    "从下面代码可知，在给 n 个元素排序时，插入排序算法需要遍历 n–1 轮。循环从位置 1 开始，直到位置 n–1 结束，这些元素都需要被插入到有序子列表中。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "16978f2c-7a6d-4485-b18a-298510202810",
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertion_sort(alist):\n",
    "    for index in range(1, len(alist)):\n",
    "        currentvalue = alist[index]\n",
    "        position = index\n",
    "\n",
    "        while position > 0 and alist[position-1] > currentvalue:\n",
    "            alist[position] = alist[position-1]\n",
    "            position = position-1\n",
    "\n",
    "        alist[position] = currentvalue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "f08fdc6d-a95c-416b-94f6-71978cf7a219",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "before sorting: [54, 26, 93, 17, 77, 31, 44, 55, 20]\n",
      "after sorting: [17, 20, 26, 31, 44, 54, 55, 77, 93]\n"
     ]
    }
   ],
   "source": [
    "a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]\n",
    "print(f\"before sorting: {a_list}\")\n",
    "insertion_sort(a_list)\n",
    "print(f\"after sorting: {a_list}\")\n",
    "assert a_list == sorted(a_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "997fbe85-6625-4539-9e44-9fea1f37b79e",
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint, seed\n",
    "seed(13)\n",
    "lst_to_sort = [randint(100, 999) for _ in range(1000)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "9414ee37-62c3-4b85-8d47-9c013e29ba05",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "61.1 μs ± 1.2 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit insertion_sort(lst_to_sort)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "00f4c64e-28eb-47a4-9bca-8a22cdedf42a",
   "metadata": {},
   "source": [
    "在最坏情况下，插入排序算法的比较次数是前 n–1 个整数之和，对应的时间复杂度是 $O(n^2)$ 。在最好情况下（列表已经是有序的），每一轮只需比较一次。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6bf696a4-35df-430d-ae57-e4df7c3fa8e9",
   "metadata": {},
   "source": [
    "移动操作和交换操作有一个重要的不同点。总体来说，交换操作的处理时间大约是移动操作的 3 倍，因为后者只需进行一次赋值。在基准测试中，插入排序算法的性能很不错。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5686f630-372f-4c8f-a87b-f1bd982fcb32",
   "metadata": {},
   "source": [
    "### 参考文档\n",
    "《Python数据结构与算法分析（第2版）》：5.3.3 插入排序"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
